public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
    public  boolean search(int val){
       if (root==null){
           return false;
       }
       TreeNode cur=root;
       while (root!=null){
           if (cur.val<val){
               cur=cur.right;
           } else if (cur.val>val) {
               cur=cur.left;
           }else {
               return true;
           }
       }
       return false;
    }
    public void insert(int val){
        if (root==null){
            root=new TreeNode(val);
            return;
        }
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
            if (cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if (cur.val>val){
                parent=cur;
                cur=cur.left;
            }else {
                return;
            }
        }
        TreeNode treeNode=new TreeNode(val);
        if (parent.val>val){
            parent.left=treeNode;
        }else if (parent.val<val){
            parent.right=treeNode;
        }
    }
    public void remove(int val){
        TreeNode cur=root;
        TreeNode parent=null;
        while (cur!=null){
            if (cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if (cur.val>val){
                parent=cur;
                cur=cur.left;
            }else {
                removeNode(cur,parent);
                return;
            }
        }
    }

    private void removeNode(TreeNode cur, TreeNode parent) {
    }
}
